//给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
//示例 1：
//输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
//输出：6
//解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
//示例 2：
//输入：height = [4,2,0,3,2,5]
//输出：9

//提示：
//n == height.length
//1 <= n <= 2 * 10e4
//0 <= height[i] <= 10e5


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int, int>> pos_hgt{};
class Solution {
public:
    int trap(vector<int>& height) {
        int ans=0;
        int length = int(height.size());
        if (length<3) return 0;
        //TODO 单调递增或递减没有考虑
        bool exit_flag= false;
        int ans_last=0;
        while(!exit_flag){
            int l=0, r=0;
            while(l< length-1 and height[l] <= height[l+1]) {l++; r++;}
            while(r < length){
                if((r==0 or height[r]>=height[r-1]) and (r==length-1 or height[r]>height[r+1]) and l!=r){
                    for(int j=l+1; j<r;j++){
                        int tmp_height = min(height[l], height[r]);
                        int dh = max(tmp_height-height[j], 0);
                        height[j] += dh;
                        ans += dh;
                    }
                    l = r;
                }
                ++r;
            }
            if (ans_last == ans) {
                exit_flag= true;
                return ans;
            }
            ans_last =ans;
        }


        return ans;
    }

private:

};

int main() {
    vector<int> input0 = {0,1,0,2,1,0,1,3,2,1,2,1};
    vector<int> input1 = {4,2,0,3,2,5};
    vector<int> input2 = {4,2,0,3,2,4,3,4};
    Solution solution;
    auto &input = input2;
    int ans = solution.trap(input);
    cout<<"answer = "<<ans<<endl;
    return 0;
}
